Định nghĩa ban đầu (truyền điểm)

Cách định nghĩa đầu tiên của mã Reed-Solomon[1] là mã hóa k ký hiệu bằng cách xem chúng như hệ số của một đa thức p(x) bậc k-1 trên một trường hữu hạn kích thước N, và tính giá trị của đa thức đó tại n>k điểm. Tính giá trị của một đa thức bậc k-1 tại hơn k điểm tạo ra một hệ phương trình nhiều phương trình hơn số ẩn số, đo đó cho phép tìm lại k hệ số từ n giá trị thông qua nội suy. n có thể nhận mọi giá trị không quá N.

Giả sử (x1, x2,..., xn) là một danh sách gồm n phần tử khác nhau của trường F. Bộ mã C được tạo từ các dãy n phần tử nhận được từ việc tính giá trị một đa thức bậc nhỏ hơn k bất kì trên trường F tại các giá trị xi.

C = { ( f ( x 1 ) , f ( x 2 ) , … , f ( x n ) ) | f ∈ F [ x ] , d e g ( f ) < k } {\displaystyle C=\{(f(x_{1}),f(x_{2}),\ldots ,f(x_{n}))|f\in F[x],deg(f)<k\}}

trong đó F[x] là vành đa thức trên F, và k, n được chọn sao cho 1≤ k ≤ n ≤ N.

Giả sử α là một phần tử sinh của nhóm nhân của F. Dãy (x1, x2,..., xn) với n=N có thể được chọn là ( 0 , α 0 , α 1 , … , α N − 2 {\displaystyle (0,\alpha ^{0},\alpha ^{1},\ldots ,\alpha ^{N-2}} .

Khi loại bỏ 0 khỏi dãy trên, do αN−1 = 1, với mọi đa thức p(x), đa thức p(αx) cũng là một đa thức cùng bậc, và mã của nó chính là mã của p(x) xoay trái một vị trí. Do đó mã Reed-Solomon có thể được xem là một mã vòng.

Định nghĩa cổ điển dưới dạng mã BCH

Mỗi ký hiệu mã có thể được xem là một hệ số của đa thức tích s(x) bằng tích của đa thức nguồn p(x) với một đa thức sinh g(x) bậc t=N-k-1. Giả sử α {\displaystyle \alpha } là một phần tử sinh của nhóm nhân trong trường hữu hạn đã cho. Đa thức sinh g(x) được định nghĩa là đa thức có α , α 2 , … , α t {\displaystyle \alpha ,\alpha ^{2},\ldots ,\alpha ^{t}} là nghiệm.

g ( x ) = ( x − α ) ( x − α 2 ) ⋯ ( x − α t ) = g 0 + g 1 x + ⋯ + g t − 1 x t − 1 + x t {\displaystyle g(x)=(x-\alpha )(x-\alpha ^{2})\cdots (x-\alpha ^{t})=g_{0}+g_{1}x+\cdots +g_{t-1}x^{t-1}+x^{t}}

Người gửi gửi đi N-1 hệ số của s(x)=p(x)g(x) và người nhận chia đa thức nhận được cho đa thức g(x) để xác định xem mã nhận được có lỗi hay không. Nếu phần dư khác không thì mã nhận được có lỗi. Đặt r(x) là đa thức dư của phép chia trên. Người nhận có thể tính giá trị của r(x) tại các nghiệm của g(x) và xây dựng một hệ phương trình để tìm ra các lỗi[2][3].

Mã Reed-Solomon là một trường hợp đặc biệt của một lớp rộng hơn, gọi là mã BCH. Thuật toán Berlekamp-Massey được thiết kế để giải mã cho mã BCH, và do đó cũng dùng được cho mã Reed-Solomon. Có thể thấy mã Reed-Solomon là một trường hợp đặc biệt của mã BCH dễ dàng hơn trong một định nghĩa khác của mã Reed-Solomon sau đây.

Cho trước một trường F kích thước q. Giả sử n = q-1 và α là một phần tử sinh của nhóm nhân của F. Cũng giả sử được cho trước 1≤ k ≤ n. Mã Reed-Solomon với các tham số trên có chứa mã tự ( f 0 , f 1 , … , f n − 1 ) {\displaystyle (f_{0},f_{1},\ldots ,f_{n-1})} khi và chỉ khi α , α 2 , … , α n − k {\displaystyle \alpha ,\alpha ^{2},\ldots ,\alpha ^{n-k}} là nghiệm của đa thức p ( x ) = f 0 + f 1 x + ⋯ + f n − 1 x n − 1 {\displaystyle p(x)=f_{0}+f_{1}x+\cdots +f_{n-1}x^{n-1}}

Với định nghĩa này, rõ ràng mã Reed-Solomon là một mã đa thức, và cụ thể hơn là một mã BCH. Đa thức sinh g(x) là đa thức nhỏ nhất với nghiệm α, α2,..., αn-k, và các mã tự chính là các đa thức chia hết cho g(x).

Sự tương đương của hai định nghĩa

Thoạt nhìn, hai định nghĩa của mã Reed-Solomon là rất khác nhau.

Sự tương đương của hai định nghĩa có thể chứng minh bằng biến đổi Fourier rời rạc. Phép biến đổi này cho thấy sự đối ngẫu giữa hệ số của một đa thức và giá trị của nó. Tính đối ngẫu này có thể được tóm tắt như sau: giả sử p(x) và q(x) là hai đa thức bậc không quá n. Nếu các giá trị của p(x) là các hệ số của q(x) thì với một tỉ lệ và hoán vị thích hợp, các giá trị của q(x) chính là các hệ số của p(x). Cụ thể hơn, giả sử α là một căn bậc n nguyên thủy của đơn vị. Các giá trị được tính tại x = αi, với i=0, 1,..., n-1. Giả sử

p ( x ) = v 0 + v 1 x + v 2 x 2 + ⋯ + v n − 1 x n − 1 , {\displaystyle p(x)=v_{0}+v_{1}x+v_{2}x^{2}+\cdots +v_{n-1}x^{n-1},}

q ( x ) = f 0 + f 1 x + f 2 x 2 + ⋯ + f n − 1 x n − 1 {\displaystyle q(x)=f_{0}+f_{1}x+f_{2}x^{2}+\cdots +f_{n-1}x^{n-1}}

và giả sử p(x) và q(x) được liên hệ bởi phép biến đổi Fourier rời rạc. Khi đó, với mọi i=0, 1,..., n-1, ta có fi=p(αi) và v i = 1 n q ( α n − i ) {\displaystyle v_{i}={\frac {1}{n}}q(\alpha ^{n-i})} .

Sử dụng các tính chất này ta nhận thấy (f0, f1,..., fn-1) là một mã tự của mã Reed-Solomon theo định nghĩa thứ nhất

• khi và chỉ khi p(x) có bậc nhỏ hơn k
• khi và chỉ khi vi=0 với i=k,..., n-1,
• khi và chỉ khi q(αi)=0 với i=1,..., n-k
• khi và chỉ khi (f0, f1,..., fn-1) là một mã tự của mã Reed-Solomon theo định nghĩa thứ hai.

Do đó, hai định nghĩa là tương đương.